package com.cdream.basic.algorithm.leetcode.dfs;


import java.util.*;

/**
 * @author cdream
 * @date 2022/7/27
 */
public class QuestionCave {
    public static void main(String[] args) {
        // start-A
        // start-b
        // A-c
        // A-b
        // b-d
        // A-end
        // b-end
        // {"start","A"},
        // {"start","b"},
        // {"A","c"},
        // {"A","b"},
        // {"b","d"},
        // {"A","end"},
        // {"b","end"},
        // dc-end
        // HN-start
        // start-kj
        // dc-start
        // dc-HN
        // LN-dc
        // HN-end
        // kj-sa
        // kj-HN
        // kj-dc

        new QuestionCave().searchPath(new String[][]{
                        {"fs","end"},
                        {"he","DX"},
                        {"fs","he"},
                        {"start","DX"},
                        {"pj","DX"},
                        {"end","zg"},
                        {"zg","sl"},
                        {"zg","pj"},
                        {"pj","he"},
                        {"RW","he"},
                        {"fs","DX"},
                        {"pj","RW"},
                        {"zg","RW"},
                        {"start","pj"},
                        {"he","WI"},
                        {"zg","he"},
                        {"pj","fs"},
                        {"start","RW"}
        });
    }
    // 保存结果
    List<List<String>> res = new ArrayList<>();
    // 记录使用过的set
    Set<String> used = new HashSet<>();
    public void searchPath(String[][] paths){
        // 构建一个双向图
        Map<String, List<String>> map = new HashMap<>();
        for (String[] path : paths) {
            List<String> list0 = map.getOrDefault(path[0], new ArrayList<>());
            list0.add(path[1]);
            map.put(path[0],list0);

            List<String> list1 = map.getOrDefault(path[1], new ArrayList<>());
            list1.add(path[0]);
            map.put(path[1],list1);
        }
        // 深度优先搜索路径
        dfs(Arrays.asList("start"),map,new ArrayList<>());
        System.out.println("所有的结果数量："+res.size());

        System.out.println("所有的结果："+res);
    }

    private void dfs(List<String> nextList, Map<String, List<String>> map,List<String> path) {
        // 如果结果集不为空，并且最后一个单词是"end"，则作为正确答案保存
        if (!path.isEmpty() && "end".equals(path.get(path.size()-1))){
            res.add(new ArrayList<>(path));
            return;
        }
        // 当前节点可以到达的下一个节点
        for (String next : nextList) {
            // 判断已经走过的小写节点是否走过，大写的不需要判断
            if (used.contains(next)){
                continue;
            }
            // 如果没有走过，加入到结果集
            path.add(next);
            // 如果这个节点是小写的塞到used集合中
            if (Character.isLowerCase(next.charAt(0))){
                used.add(next);
            }
            // 获取next可达的下一个节点，递归查找
            List<String> nexts = map.get(next);
            dfs(nexts, map, path);
            // 将next移除，进入下一个循环
            path.remove(path.size()-1);
            used.remove(next);
        }
    }
}
